package main

import (
	"bytes"
	"fmt"
)

//#link: https://leetcode-cn.com/problems/sort-characters-by-frequency/
func main() {
	s := "abavc"
	fmt.Println(frequencySort(s))
}

//桶排序
func frequencySort(s string) string {
	tempMap := make(map[byte]int)
	maxFre := 0
	for _, b := range []byte(s) {
		tempMap[b]++
		maxFre = max(maxFre, tempMap[b])
	}

	bucket := make([][]byte, maxFre+1)
	for index, value := range tempMap {
		bucket[value] = append(bucket[value], index)
	}

	result := make([]byte, 0)
	for i := maxFre; i >= 1; i-- {
		for _, b := range bucket[i] {
			result = append(result, bytes.Repeat([]byte{b}, i)...)
		}
	}

	return string(result)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
